package com.zhang.study.chapter02;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

import static com.zhang.util.RandomArrayUtil.generateRandomArrayWithOddAndEven;

/**
 * @author zhang
 * @date 2023/11/22 11:09
 * 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
 */
public class Code02_printOddTimesNum2 {

    /**
     * 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数 a!=b
     *
     * @param arr 数组
     *            1. 将数组依次全部异或 假设 a出现了奇数次 b也出现了奇数次 那么全部异或后 结果就是 a^b
     */
    public static String printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int i : arr) {
            eor ^= i;
        }
        // a 和 b 是两种数 且 a!=b  那么 eor != 0

        // 将eor中最右侧的1提取出来
        int rightOne = eor & (-eor);
        // 假设rightOne 是: 000001000
        // 现在情况有两种 : 而且a 和 b 是分开的 因为如果都有1 那么第四位应该是 0
        // 1. arr中的数在rightOne中有1的 (其中有arr中的部分偶数)
        // 2. arr中的数在rightOne中没有1的 (其中有arr中的另一部分部分偶数)
        int a = 0;
        for (int i : arr) {
            // 因为假设a在rightOne中有1 那么a^i 应该是 a  因为在里面有a和部分偶数 偶数异或后是0 就只剩下 a 了
            if ((i & rightOne) != 0) {
                a ^= i;
            }
        }
        int b = a ^ eor; // 因为 eor 异或后是 a^b 现在求出来a 那么 b = a^eor
        return a + " " + b;
    }

    public static String test(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        HashSet<Integer> integers = new HashSet<>();
        for (int i : arr) {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);
            }
        }
        for (int i : arr) {
            if (map.get(i) % 2 == 1) {
                if(!integers.contains(i)){
                    sb.append(i).append(" ");
                    integers.add(i);
                }
            }
        }
        return sb.toString().isEmpty() ?"   ": sb.substring(0, sb.length() - 1);
    }


    public static void main(String[] args) {
        int maxSize = 100; // 假设最大长度为10
        int maxVal = 100; // 假设允许的最大值为100
        int times = 1000000;
        for (int i = 0; i < times; i++) {
            int[] randomArray = generateRandomArrayWithOddAndEven(maxSize, maxVal, 2);
            String[] ans1 = printOddTimesNum2(randomArray).split(" ");
            String[] ans2 = test(randomArray).split(" ");
            for (int j = 0; j < ans1.length; j++) {
                int finalJ = j;
                if(Arrays.stream(ans2).noneMatch(a -> a.equals(ans1[finalJ]))){
                    System.out.println("ans1 = " + Arrays.toString(ans1));
                    System.out.println("ans2 = " +Arrays.toString(ans2));
                    System.out.println("randomArray = " +Arrays.toString(randomArray));
                    return;
                }
            }

        }
        System.out.println("Nice!");
    }

}
